#ifndef ASTAR_H
#define ASTAR_H

#include <cstdlib>
#include <set>
#include "direction.h"

template <typename T>
struct Compare : public std::binary_function<T,T,bool>{
  bool operator() (const T& a, const T& b) {return (a.G() < b.G());}
};

template <typename Loc>
class AStar
{
    public:
        AStar(Loc resolution) : m_map_resolution(resolution){}

        void Find(const Loc& from, const Loc& to, t_path& out)
        {
            PointInfo start(from);
            t_path result;

            PointSet marked_points;

            marked_points.insert(start);

            //while (start.F(to) > 1)
            {

                marked_points.insert(PointInfo(start,EAST));
                marked_points.insert(PointInfo(start,WEST));
                marked_points.insert(PointInfo(start,NORD));
                marked_points.insert(PointInfo(start,SOUTH));
            }

            out.clear();
            out.push_back(EAST);
            out.push_back(EAST);
            //std::copy(result.begin(), result.end(), out.begin());
        }
    protected:


    private:
        typedef int step;
        class PointInfo;

        class PointInfo{
            public:
                PointInfo(Loc start) : m_pos(start), m_step(0) {}
                PointInfo(PointInfo parent, t_direction dir) : m_pos(parent.m_pos), m_step(parent.m_step) { Move(dir);}

                step G() const {return m_step;}
                step H(const Loc& loc) const {return std::abs(m_pos.row - loc.row) + std::abs(m_pos.col - loc.col);}
                step F(const Loc& loc) const {return G() + H(loc);}

            private:
                void Move(t_direction direction)
                {
                    switch (direction)
                    {
                        //TODO: usage map resolution
                        case NORD: --m_pos.row; break;
                        case WEST: --m_pos.col; break;
                        case SOUTH: ++m_pos.row; break;
                        case EAST: ++m_pos.row; break;
                        default: //TODO: throw exception
                            return;
                        ++m_step;
                    }

                }
            private:
                Loc m_pos;
                step m_step;
        };

        typedef std::set<PointInfo, Compare<PointInfo> > PointSet;

    private:
        Loc m_map_resolution;
};

#endif // ASTAR_H
